//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>
#include <iterator>
#include <random>


/**
 * @brief 从 位置 [left, right] 的范围内均匀返回一个值(均匀分布, 概率相同)。
 * @param left 范围的左边界
 * @param right 范围的右边界
 * @return 返回这个范围内的一个值。
 */
static int generate(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


/**
 * @brief 生成一个 [0, 1) 范围内的连续均匀分布的 double 值。
 * @return 返回生成的 double 值。
 */
static double randomNumber() {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    return std::generate_canonical<double, 10>( randomEngine );
}


static std::vector<int> partition(std::vector<int>& arr, int l, int r) {
    int less = l - 1;
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            std::swap( arr[++less], arr[l++] );
        } else if (arr[l] > arr[r]) {
            std::swap( arr[--more], arr[l] );
        } else {
            l++;
        }
    }
    std::swap( arr[more], arr[r] );
    return std::vector<int>{less + 1, more};
}


static void quickSort(std::vector<int>& arr, int l, int r) {
    if (l < r) {
        // 随机选一个数把这个数与最右侧的数交换。
        /*
         * Math.random()是令系统随机选取大于等于 0.0 且小于 1.0 的伪随机 double 值，是Java语言常用代码。
         * 例如：double a=Math.random()*(3-1)+1，设置一个随机1到3的变量。
         *
         * 产生一个[0，1)之间的随机数
         *
         * Math.random() * (n-m) + m
         */
//        swap(arr, l + (int)(Math.random() * (r - l + 1)), r);

        // 这句是可以的。
//        std::swap( arr[generate( l, r )], arr[r] );
        // 这句也是可以的。
        std::swap( arr[l + static_cast<int>((randomNumber() * (r - l + 1)))], arr[r] );
        std::vector<int> p = partition( arr, l, r );
        quickSort( arr, l, p[0] - 1 );
        quickSort( arr, p[1] + 1, r );
    }
}


static void quickSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    quickSort( arr, 0, arr.size() - 1 );
}


int main(int argc, char** argv) {
    std::vector<int> arr{1, 41, 5, 61, 2, 6, 671, 761, 14, 61};
    quickSort( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;


    return 0;
}
